home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / mac / raytrace / rayshade / ryshdmst.hqx / Rayshade / Source / poly.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-06  |  7.7 KB  |  336 lines
  1. /*
  2.  * poly.c
  3.  *
  4.  * Copyright (C) 1989, 1991, Craig E. Kolb
  5.  * All rights reserved.
  6.  *
  7.  * This software may be freely copied, modified, and redistributed
  8.  * provided that this copyright notice is preserved on all copies.
  9.  *
  10.  * You may not distribute this software, in whole or in part, as part of
  11.  * any commercial product without the express consent of the authors.
  12.  *
  13.  * There is no warranty or other guarantee of fitness of this software
  14.  * for any purpose.  It is provided solely "as is".
  15.  *
  16.  * $Id: poly.c,v 4.0 91/07/17 14:39:00 kolb Exp Locker: kolb $
  17.  *
  18.  * $Log:    poly.c,v $
  19.  * Revision 4.0  91/07/17  14:39:00  kolb
  20.  * Initial version.
  21.  * 
  22.  */
  23. #include "geom.h"
  24. #include "poly.h"
  25.  
  26. Methods *iPolygonMethods = NULL;
  27. static char polyName[] = "polygon";
  28.  
  29. unsigned long PolyTests, PolyHits;
  30.  
  31. /*
  32.  * Create a reference to a polygon with vertices equal to those
  33.  * on the linked-list "plist."
  34.  */
  35. RPolygon *
  36. PolygonCreate(plist, npoints, flipflag)
  37. PointList *plist;
  38. int npoints, flipflag;
  39. {
  40.     RPolygon *poly;
  41.     Float indexval;
  42.     Vector *prev, *cur, anorm;
  43.     PointList *curp, *pltmp;
  44.     int i;
  45.  
  46.     poly = (RPolygon *)share_malloc(sizeof(RPolygon));
  47.     /*
  48.      * Allocate space for the vertices.
  49.      */
  50.     poly->points = (Vector *)Malloc((unsigned)(npoints*sizeof(Vector)));
  51.     poly->npoints = npoints;
  52.  
  53.     /*
  54.      * Copy the vertices from the linked list to the array, freeing
  55.      * the linked list as we go so that the caller doesn't have
  56.      * to worry about doing so.
  57.      */
  58.     i = npoints -1;
  59.     for(curp = plist; curp != (PointList *)0; curp = pltmp) {
  60.         poly->points[i--] = curp->vec;
  61.         pltmp = curp->next;
  62.         Free((voidstar)curp);
  63.     }
  64.  
  65.     /*
  66.      * Find normal to polygon.
  67.      */
  68.     poly->norm.x = poly->norm.y = poly->norm.z = 0.;
  69.     prev = &poly->points[poly->npoints -1];
  70.     for(i = 0,cur = poly->points;i < poly->npoints;i++, prev = cur, cur++) {
  71.         poly->norm.x += (prev->y - cur->y) * (prev->z + cur->z);
  72.         poly->norm.y += (prev->z - cur->z) * (prev->x + cur->x);
  73.         poly->norm.z += (prev->x - cur->x) * (prev->y + cur->y);
  74.     }
  75.  
  76.     if (VecNormalize(&poly->norm) == 0.) {
  77.         /*
  78.          * Degenerate normal --> degenerate polygon
  79.          */
  80.         RLerror(RL_WARN, "Degenerate polygon.\n",0,0,0);
  81.         Free((voidstar)poly->points);
  82.         return (RPolygon *)NULL;
  83.     }
  84.  
  85.     /*
  86.      * If filflag is true, flip the normal.
  87.      */
  88.     if (flipflag)
  89.         VecScale(-1, poly->norm, &poly->norm);
  90.  
  91.     /*
  92.      * Compute and store the plane constant.
  93.      */
  94.     poly->d = dotp(&poly->norm, &poly->points[0]);
  95.  
  96.     /*
  97.      * Find the "dominant" part of the normal vector.  This
  98.      * is used to turn the point-in-polygon test into a 2D problem.
  99.      */
  100.     anorm.x = fabs(poly->norm.x);
  101.     anorm.y = fabs(poly->norm.y);
  102.     anorm.z = fabs(poly->norm.z);
  103.     indexval = max(anorm.y, anorm.z);
  104.     indexval = max(anorm.x, indexval);
  105.  
  106.     if (indexval == anorm.x)
  107.         poly->index = XNORMAL;
  108.     else if (indexval == anorm.y)
  109.         poly->index = YNORMAL;
  110.     else
  111.         poly->index = ZNORMAL;
  112.  
  113.     return poly;
  114. }
  115.  
  116. Methods *
  117. PolygonMethods()
  118. {
  119.     if (iPolygonMethods == (Methods *)NULL) {
  120.         iPolygonMethods = MethodsCreate();
  121.         iPolygonMethods->create = (GeomCreateFunc *)PolygonCreate;
  122.         iPolygonMethods->methods = PolygonMethods;
  123.         iPolygonMethods->name = PolygonName;
  124.         iPolygonMethods->intersect = PolygonIntersect;
  125.         iPolygonMethods->normal = PolygonNormal;
  126.         iPolygonMethods->uv = PolygonUV;
  127.         iPolygonMethods->bounds = PolygonBounds;
  128.         iPolygonMethods->stats = PolygonStats;
  129.         iPolygonMethods->checkbounds = TRUE;
  130.         iPolygonMethods->closed = FALSE;
  131.     }
  132.     return iPolygonMethods;
  133. }
  134.  
  135. /*
  136.  * Quadrants are defined as:
  137.  *        |
  138.  *   1    |   0
  139.  *        |
  140.  * -------c--------
  141.  *        |
  142.  *   2    |   3
  143.  *        |
  144.  */
  145. #define quadrant(p, c) ((p.u<c.u) ? ((p.v<c.v) ? 2 : 1) : ((p.v<c.v) ? 3 : 0))
  146.  
  147. /*
  148.  * Perform ray-polygon intersection test.
  149.  */
  150. int
  151. PolygonIntersect(poly, ray, mindist, maxdist)
  152. RPolygon *poly;
  153. Ray *ray;
  154. Float mindist, *maxdist;
  155. {
  156.     register int winding, i;
  157.     Vector dir, pos;
  158.     int quad, lastquad;
  159.     Float dist, left, right;
  160.     Vec2d center, cur, last;
  161.  
  162.     PolyTests++;
  163.     pos = ray->pos;
  164.     dir = ray->dir;
  165.     /*
  166.      * First, find where ray hits polygon plane, projecting
  167.      * along the polygon's dominant normal component.
  168.      */
  169.  
  170.     dist = dotp(&poly->norm, &dir);
  171.     if(fabs(dist) < EPSILON)
  172.         /*
  173.           * No intersection with polygon plane.
  174.          */
  175.         return FALSE;
  176.  
  177.     dist = (poly->d - dotp(&poly->norm, &pos)) / dist;
  178.     if(dist < mindist || dist > *maxdist)
  179.         /*
  180.          * Intersection point behind origin or too far.
  181.          */
  182.         return FALSE;
  183.  
  184.     /*
  185.      * Compute the point of intersection, projected appropriately.
  186.      */
  187.     if(poly->index == XNORMAL) {
  188.         center.u = pos.y + dist * dir.y;
  189.         center.v = pos.z + dist * dir.z;
  190.     } else if(poly->index == YNORMAL) {
  191.         center.v = pos.z + dist * dir.z;
  192.         center.u = pos.x + dist * dir.x;
  193.     } else  {
  194.         center.u = pos.x + dist * dir.x;
  195.         center.v = pos.y + dist * dir.y;
  196.     }    
  197.  
  198.     /*
  199.      * Is the point inside the polygon?
  200.      *
  201.      * Compute the winding number by finding the quadrant each
  202.      * polygon point lies in with respect to the the point in
  203.      * question, and computing a "delta" (winding number).  If we
  204.      * end up going around in a complete circle around
  205.      * the point (winding number is non-zero at the end), then
  206.      * we're inside.  Otherwise, the point is outside.
  207.      *
  208.      * Note that we can turn this into a 2D problem by projecting
  209.      * all the points along the axis defined by poly->index,
  210.      * the "dominant" part of the polygon's normal vector.
  211.      */
  212.     winding = 0;
  213.     VecProject(last, poly->points[poly->npoints -1], poly->index);
  214.     lastquad = quadrant(last, center);
  215.     for(i = 0; i < poly->npoints; i++, last = cur) {
  216.         VecProject(cur, poly->points[i], poly->index);
  217.         quad = quadrant(cur, center);
  218.         if (quad == lastquad)
  219.             continue;
  220.         if(((lastquad + 1) & 3) == quad)
  221.             winding++;
  222.         else if(((quad + 1) & 3) == lastquad)
  223.             winding--;
  224.         else {
  225.             /*
  226.              * Find where edge crosses
  227.              * center's X axis.
  228.              */
  229.             right = last.u - cur.u;
  230.             left = (last.v - cur.v) * (center.u - last.u);
  231.             if(left + last.v * right > right * center.v)
  232.                 winding += 2;
  233.             else
  234.                 winding -= 2;
  235.         }
  236.         lastquad = quad;
  237.     }
  238.  
  239.     if (winding != 0) {
  240.         *maxdist = dist;
  241.         PolyHits++;
  242.         return TRUE;
  243.     }
  244.     return FALSE;
  245. }
  246.  
  247. /*
  248.  * Return the normal to the polygon surface.
  249.  */
  250. /*ARGSUSED*/
  251. int
  252. PolygonNormal(poly, pos, nrm, gnrm)
  253. RPolygon *poly;
  254. Vector *pos, *nrm, *gnrm;
  255. {
  256.     *gnrm = *nrm = poly->norm;
  257.     return FALSE;
  258. }
  259.  
  260. /*ARGSUSED*/
  261. void
  262. PolygonUV(poly, pos, norm, uv, dpdu, dpdv)
  263. RPolygon *poly;
  264. Vector *pos, *norm, *dpdu, *dpdv;
  265. Vec2d *uv;
  266. {
  267.     /*
  268.      * Since there's no nice way to do this, we wimp out and
  269.      * do the following...
  270.      *
  271.      * Of course, we could force the user to specify U and V
  272.      * axes, but forcing them to use X and Y as U and V is
  273.      * just as arbitrary and much simpler to deal with.
  274.      */
  275.     uv->u = pos->x;
  276.     uv->v = pos->y;
  277.     if (dpdu) {
  278.         dpdu->x = 1.;
  279.         dpdu->y = dpdu->z = 0.;
  280.         dpdv->x = dpdv->z = 0.;
  281.         dpdv->y = 1.;
  282.     }
  283. }
  284.  
  285. /*
  286.  * Compute the extent of a polygon
  287.  */
  288. void
  289. PolygonBounds(poly, bounds)
  290. RPolygon *poly;
  291. Float bounds[2][3];
  292. {
  293.     register int i;
  294.  
  295.     bounds[LOW][X] = bounds[HIGH][X] = poly->points[0].x;
  296.     bounds[LOW][Y] = bounds[HIGH][Y] = poly->points[0].y;
  297.     bounds[LOW][Z] = bounds[HIGH][Z] = poly->points[0].z;
  298.  
  299.     for (i = 1 ;i < poly->npoints; i++) {
  300.         if (poly->points[i].x < bounds[LOW][X])
  301.             bounds[LOW][X] = poly->points[i].x;
  302.         if (poly->points[i].x > bounds[HIGH][X])
  303.             bounds[HIGH][X] = poly->points[i].x;
  304.         if (poly->points[i].y < bounds[LOW][Y])
  305.             bounds[LOW][Y] = poly->points[i].y;
  306.         if (poly->points[i].y > bounds[HIGH][Y])
  307.             bounds[HIGH][Y] = poly->points[i].y;
  308.         if (poly->points[i].z < bounds[LOW][Z])
  309.             bounds[LOW][Z] = poly->points[i].z;
  310.         if (poly->points[i].z > bounds[HIGH][Z])
  311.             bounds[HIGH][Z] = poly->points[i].z;
  312.     }
  313. }
  314.  
  315. char *
  316. PolygonName()
  317. {
  318.     return polyName;
  319. }
  320.  
  321. void
  322. PolygonStats(tests, hits)
  323. unsigned long *tests, *hits;
  324. {
  325.     *tests = PolyTests;
  326.     *hits = PolyHits;
  327. }
  328.  
  329. void
  330. PolygonMethodRegister(meth)
  331. UserMethodType meth;
  332. {
  333.     if (iPolygonMethods)
  334.         iPolygonMethods->user = meth;
  335. }
  336.